package leetcode;

import java.util.Arrays;

/**
 * description:
 * author:张腾
 * date:2021-06-23
 */
//获取最长递增子序列的序列
public class leetcode300_2  {
    public static void main(String[] args) {
        System.out.println(lengthOfLIS(new int[]{2, 1, 5, 3, 6, 4, 8, 9, 7}));
    }
    public static int[] lengthOfLIS(int[] nums) {
        int len=1, n=nums.length;
        if (n==0) return null;
        //表示 可能的最长子序列
        int[] d = new int[n+1];
        //表示 以该位置结尾的最长子序列长度
        int dp[] = new int[n];
        d[len] = nums[0];
        dp[0] = len;
        for (int i = 1; i < n; i++) {
            if (nums[i]>d[len]) {
                d[++len] = nums[i];
                dp[i] = len;
            }
            else {
                int l=1, r=len, pos=0;
                //pos为d数组中小于nums[i]的前一位
                while (l<=r){
                    int mid = (l+r)>>1;
                    if (d[mid]<nums[i]){
                        pos = mid;
                        l = mid+1;
                    }else{
                        r = mid-1;
                    }
                }
                d[pos+1] = nums[i];
                dp[i] = pos+1;
            }
        }
        for (int i = n - 1 , j = len; j > 0; i--) {
            if (dp[i]==j) d[j--] = nums[i];
        }
        int[] res = new int[len];
        System.arraycopy(d,1,res,0,len);
        return res;
    }
}
